binary search tree中，本來遵守著從中間Node切開，左邊小於右邊的規則，但是現在有其中兩個Node錯置了。

資料錯誤要怎麼修正？

從來沒做過。

思路

要找到不符合規則的點，第一直覺是，判斷這棵樹是不是BST，但除此之外沒有任何想法。

吸收知識時間

晃一晃腦子，看能不能把知識晃出來，啊結果只有水...

忘了一件事，二元樹的結構的其中一個性質：可以用一維陣列儲存，然後用index去存取特定節點，像是：index從1開始的話，1是root，每個節點index=i，則左小孩index=2*i，右小孩index=2*i+1，而自己的index/2則是父的節點index。

這樣的話，一維陣列很好處理啊，只要sort，再放值回去就好。

但是

啊哈，但是題目給的二元樹，是用struct建立起來的呢！

實在沒想法。

C++筆記

// first為 準備指向型態為TreeNode 的指標，現在還沒指向任何TreeNode
TreeNode* first = NULL; 

//cout << first; // stdout: 0
//cout << first->val; // error

//新增一個TreeNode變數，同時賦最小Int常數給val。並將此新TreeNode交給指標prev指著。
TreeNode* prev = new TreeNode(INT_MIN); 

//cout << prev->val; //stdout: -2147483648

程式碼

class Solution {
public:
    TreeNode* first = NULL;
    TreeNode* second = NULL;
    TreeNode* prev = new TreeNode(INT_MIN);
    
    void inorder(TreeNode* curr) {
        if (curr == NULL)
            return;
        inorder(curr->left);
        if (first == NULL && prev->val > curr->val)
            first = prev;
        if (first != NULL && prev->val > curr->val)
            second = curr;
        prev = curr;
        inorder(curr->right);
    }    
    
    void recoverTree(TreeNode* root) {
        inorder(root);
        int temp = second->val;
        second->val = first->val;
        first->val = temp;
    }
};

參考：
https://www.cnblogs.com/grandyang/p/4298069.html

https://leetcode.com/problems/recover-binary-search-tree/discuss/1499780/C%2B%2B%3A-simple-and-intuitive